/*
 * Copyright 2010 eBusinessInformation
 * 
 * Licensed under the Apache License, Version 2.0 (the "License"); you may not
 * use this file except in compliance with the License. You may obtain a copy of
 * the License at
 * 
 * http://www.apache.org/licenses/LICENSE-2.0
 * 
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
 * WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
 * License for the specific language governing permissions and limitations under
 * the License.
 */
package com.excilys.blog.refactoring.initial;

import java.util.ArrayList;
import java.util.List;
import java.util.Set;

import com.excilys.blog.refactoring.GeoPoint;
import com.excilys.blog.refactoring.HullHelper;

public class InitialHullHelper implements HullHelper {

    public List<GeoPoint> computeConvexHull(Set<GeoPoint> points) {

        // Path list
        ArrayList<GeoPoint> path = new ArrayList<GeoPoint>();

        // Pick the min longitude point as first
        GeoPoint first = null;
        for (GeoPoint point : points) {
            if (first == null || point.getLongitude() < first.getLongitude()) {
                first = point;
            }
        }

        if (first != null) {
            path.add(first);
        } else {
            throw new IllegalArgumentException("Can't retrieve the western point");
        }

        boolean right = true;
        boolean loop = true;

        while (loop) {

            GeoPoint current = path.get(path.size() - 1);

            GeoPoint next = null;
            double nextLatitudeDiff = 0;
            double nextLongitudeDiff = 0;
            boolean recordNext = false;
            for (GeoPoint point : points) {
                if (!point.equals(current)) {
                    double latitudeDiff = point.getLatitude() - current.getLatitude();
                    double longitudeDiff = point.getLongitude() - current.getLongitude();
                    if (longitudeDiff == 0 || longitudeDiff > 0 == right) {
                        if (next == null) {
                            recordNext = true;
                        } else {
                            // Compare the 'a' in the linear equation Y = a.X
                            // that correspond to the line slope.
                            boolean negativeSlope = latitudeDiff * nextLongitudeDiff - nextLatitudeDiff * longitudeDiff < 0;

                            if (negativeSlope) {
                                recordNext = true;
                            }
                        }

                        if (recordNext) {
                            recordNext = false;
                            next = point;
                            nextLatitudeDiff = latitudeDiff;
                            nextLongitudeDiff = longitudeDiff;
                        }

                    }
                }
            }

            if (next != null) {

                // Check abnormal case
                if (path.size() > points.size() + 1) {
                    throw new RuntimeException("Convex hull computation failed");
                }

                path.add(next);

                /*
                 * If we are not back to the first point, let's continue finding
                 * the path.
                 * 
                 * Otherwise, do nothing => going back from the stack, this is
                 * actually the end point of the recursive algorithm.
                 */

                if (path.get(0) == next) {
                    loop = false;
                }

            } else {
                // We have reach the point on the right, let's go back!
                right = !right;
            }
        }

        return path;
    }

}
